package org.lql.algo.codecrush.hot100.linked;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-10-11 14:47
 * @description: 25. K 个一组翻转链表 <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class ReverseKGroup {

	public ListNode reverseKGroup(ListNode head, int k) {
		ListNode dummy = new ListNode(0, head);
		ListNode last = dummy;
		while (head != null) {
			// 寻找翻转的节点
			ListNode kth = findKth(head, k);
			// 如果kth 为空，说明剩余节点不足 k 个，不需要翻转
			if (kth == null) {
				break;
			}
			// 下一组的头节点
			ListNode nextGroupHead = kth.next;
			// 进行组间翻转
			reverse(head, nextGroupHead);
			// 更新组间关系
			last.next = kth;
			head.next = nextGroupHead;
			last = head;
			head = nextGroupHead;
		}
		return dummy.next;
	}

	public ListNode findKth(ListNode head, int k) {
		while (head != null) {
			k--;
			if (k == 0) {
				return head;
			}
			head = head.next;
		}
		return null;
	}

	public void reverse(ListNode start, ListNode end) {
		ListNode last = start;
		while (start != end) {
			ListNode next = start.next;
			start.next = last;
			last = start;
			start = next;
		}
	}

	public static void main(String[] args) {
		ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
		ReverseKGroup reverseKGroup = new ReverseKGroup();
		ListNode listNode = reverseKGroup.reverseKGroup(head, 2);
		while (listNode != null) {
			System.out.print(listNode.val + " -> ");
			listNode = listNode.next;
		}
	}
}
